package bitOperation;

/**
@author city
@date 10:06 PM 2020/6/25
 
############################################# 题目描述 #############################################

137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3
示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

############################################# 题目描述 #############################################
 */
public class L137SingleNumber2 {
    public static void main(String[] args) {
        L137SingleNumber2 m = new L137SingleNumber2();
    }

    public int singleNumber(int[] nums) {
        int x1 = 0, x2 = 0;

        for(int i : nums){
            x2 = x2 ^ (x1 & i);
            x1 = x1 ^ i;

            // 掩码。因为出现3次的3，对应二进制是11，只有第一位和第二位都是1的时候，mask掩码生效。
            int mask = ~(x1 & x2);

            x2 &= mask;
            x1 &= mask;
        }

        return x2;
    }

}
